"""
3171. 找到按位或最接近 K 的子数组
困难
相关标签
premium lock icon
相关企业
提示
给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。



示例 1：

输入：nums = [1,2,4,5], k = 3

输出：0

解释：

子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：nums = [1,3,1,3], k = 2

输出：1

解释：

子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入：nums = [1], k = 10

输出：9

解释：

只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。



提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 109
"""
from typing import List


class Solution:
    def minimumDifference(self,a: List[int], k: int) -> int:
        ans = float("inf")
        for i,j in enumerate(a):
            ans = min(ans,abs(k - j))
            for z in range(i-1,-1,-1):
                #当前j是前面dp[z]子集，则该次遍历无意义，由于前面dp[0,z)是后面dp[z]的父级，所以前面也不需要跳过因为也肯定不会变化，直接跳过该次遍历
                if j|a[z] == a[z]:
                    break
                a[z] = j|a[z]
                ans = min(ans,abs(k - a[z]))
        return ans
    def minimumDifference_res1(self,a: List[int], k: int) -> int:
        min_diff =  float("inf")
        for i, x in enumerate(a):  # 计算右端点为 i 的子数组的或值，其中 x = a[i]
            min_diff = min(min_diff, abs(x - k))  # 只有 x 一个数的子数组或值就是 x
            for j in range(i - 1, -1, -1):
                if(a[j]|x == a[j]):
                    break
                a[j] |= x  # 现在 a[j] = 原数组 a[j] 到 a[i] 的或值
                min_diff = min(min_diff, abs(a[j] - k))
        return min_diff
if __name__ == '__main__':
    # print(float("inf"))
    print(Solution().minimumDifference([1,2,4,5],3))
